#include <iostream>
#include "BinarySearchTree.h"
#include<ctime>
using namespace std;
/// @brief BSTsorting模板函数，功能是将数组 _arr 排序;
/// @tparam Comparable BinarySearchTree的类型;
/// @param _arr 输入的Comparable模板类数组对象_arr，代表需要排序的数组;
/// @param _mode 代表需要排序的模式_mode;
template <typename Comparable>
void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0)
{
    int start,finish;
    BinarySearchTree<Comparable> bst{};
    if (_mode == 0)
    {
        start=clock();
        for(int times = 0 ;times < 5;times++)
        {
            for(int i = 0;i < _arr.size();i++)
            {
                bst.insert(_arr[i]);
            }
            _arr.clear();
            bst.add(_arr);
        }
        finish=clock();
        std::cout << "The sorting process costs " << (finish-start)/5 << std::endl;
    }
    if (_mode == 1)
    {
        start=clock();
        for(int times = 0 ;times < 100;times++)
        {
            srand((unsigned)time(NULL));
            random_shuffle(_arr.begin(), _arr.end()); 
            for(int j = 0;j<_arr.size() ;j++)
            {
                bst.insert(_arr[j]);
            }
            _arr.clear();
            bst.add(_arr);
        }
        finish=clock();
        std::cout << "The sorting process costs " << (finish-start)/100 << std::endl;
    }
};

/// @brief main函数，输入数组规模和模式，对于模式0,生成5次递增的数组输出排序所需要的时间平均值，对于模式1,随机生成100次该规模的数组并输出排序所需要的时间的平均值;
/// @return 执行成功，返回0;
int main( )
{
    int testsize;
    int size;
    int mode;
    while (std::cin >> testsize)
    {
        for (int i = 0;i < testsize;i++)
        {
            std::cin >> size >> mode;
            if((mode!=0 && mode !=1) || size <0)
            {
                std::cerr << "Wrong input." << std::endl;
            }
            std::vector<int> arr={};
            for(int i = 0; i< size; i++)
            {
                arr.push_back(i);
            }
            BSTSorting(arr,mode);
        }
        return 0;
    }
};
